package com.zxy.javaarithmetic.chapter_2_LinkList;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_2_LinkList
 *  @文件名:   P_8_LinkedListDivide
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/27 9:33
 *  @描述：    将链表按某值划分为左边小，中间相等，右边大的形式
 */
public class P_8_LinkedListDivide {

	public static void main(String[] args) {

		Node head = new Node(9);
		head.next = new Node(0);
		head.next.next = new Node(4);
		head.next.next.next = new Node(5);
		head.next.next.next.next = new Node(1);

		LinkListUtils.printRingNode(divideLinkedList2(head, 3));
	}

	/**
	 *  9->0->4->5->1,按3划分，结果为 1->0->4->9->5或0->1->9->4->5 都可以
	 *  普通解法，将数据存储在数组中，交换次序之后再拼接起来
	 * @param head
	 * @return
	 */
	private static Node divideLinkedList1(Node head, int pivot) {
		if (head == null) {
			return head;
		}
		//将链表数据存储在数组中
		int n = 0;
		Node node = head;
		while (node != null) {
			n++;
			node = node.next;
		}

		Node[] nodes = new Node[n];
		n = 0;
		while (head != null) {
			nodes[n] = head;
			head = head.next;
			n++;
		}

		//
		arrPartition(nodes, pivot);

		//拼接调整后的列表
		for (int i = 1; i < nodes.length; i++) {
			nodes[i - 1].next = nodes[i];
		}
		nodes[nodes.length - 1].next = null;

		return nodes[0];
	}

	/**
	 *
	 * @param nodes
	 * @param pivot
	 */
	private static void arrPartition(Node[] nodes, int pivot) {
		int small = -1;
		int big = nodes.length;
		int index = 0;

		while (index != big) {
			if (nodes[index].value < pivot) {
				swap(nodes, index++, ++small);
			} else if (nodes[index].value == pivot) {
				index++;
			} else {
				swap(nodes, index, --big);
			}
		}
	}

	private static void swap(Node[] nodes, int index1, int index2) {
		Node temp = nodes[index1];
		nodes[index1] = nodes[index2];
		nodes[index2] = temp;
	}

	/**
	 * 查分规则增加一条：划分后每个节点的顺序要和在原链表中的顺序相同，并且事件复杂度为O(n),空间额外复杂度为O(1)
	 * 9->0->4->5->1,按3划分，结果只能为 0->1->9->4->5
	 * @param head
	 * @param pivot
	 * @return
	 */
	private static Node divideLinkedList2(Node head, int pivot) {

		Node sHead = null;//小于pivot链表的头和尾
		Node sTail = null;
		Node eHead = null;//等于pivot的头和尾
		Node eTail = null;
		Node bHead = null;//大于pivot链表的头和尾
		Node bTail = null;
		Node next = null;//保存遍历过程中的下一个节点

		while (head != null) {
			next = head.next;
			head.next = null;
			if (head.value < pivot) {
				if (sHead == null) {
					sHead = head;
					sTail = head;
				} else {
					sTail.next = head;
					sTail = head;
				}
			} else if (head.value == pivot) {
				if (eHead == null) {
					eHead = head;
					eTail = head;
				} else {
					eTail.next = head;
					eTail = head;
				}
			} else {
				if (bHead == null) {
					bHead = head;
					bTail = head;
				} else {
					bTail.next = head;
					bTail = head;
				}
			}
			head = next;
		}

		if (sTail != null) {
			sTail.next = eHead;
			eTail = eTail == null ? sTail : eTail;
		}
		if (eTail != null) {
			eTail.next = bHead;
		}

		return sHead != null ? sHead : eHead != null ? eHead : bHead;
	}

}
